The present invention relates to distributed systems and methods for finding a path from a source node to a destination node where the path chosen satisfies a path constraint for a first additive path parameter and concurrently optimizes a second additive path parameter.
A goal of many carriers is to have one automatic network control structure. A new set of protocols that make up the framework of Generalized Multi-Protocol Label switching (GMPLS) provides one method to accomplish this goal. Currently, placing data on a telecommunications network involves encapsulating several layers. For example, transporting data traffic on a telecommunications network can involve stacking an Internet Protocol layer on top of an asynchronous transfer mode layer on top of a synchronous optical network layer on top of a dense wavelength division multiplexing layer. Each layer has its own management and control. Interfacing between layers typically involves manual provisioning. Different types of service providers typically manage each layer. GMPLS attempts to reduce the number of interfaces that involve manual provisioning, reduce the operational cost of the network, and improve efficiency.
In other words, GMPLS tries to extend the control plane architecture of MPLS to all non-packet switched networks. Extending the control plane architecture to these transport networks helps to make network administration more intelligent and leads to better use of available resources. One example of a non-packet switched network is a wavelength routed meshed photonic network. GMPLS provides a framework for the control plane architecture by extending MPLS component signaling and routing protocols to dense wavelength division multiplexing (DWDM) based meshed networks.
With respect to the routing protocols, the Internet engineering task force (IETF) has proposed extensions to the open shortest path first (OSPF) and intermediate system-intermediate system (IS-IS) protocols as part of GMPLS to take into consideration the special properties of meshed photonic networks. These routing protocols are intra-domain protocols and hence work within a single domain also called an autonomous system (AS). Since these routing protocols are limited to an AS, any quality of service guarantees provided by the protocols are also limited to providing guarantees within the boundaries of the AS.
Thus a need exists for a set of protocols that facilitate quality of service (QoS) routing between domains owned by different ISP's often operating on different vendor equipment. In other words, there is a need to extend QoS routing beyond one's own domain and into multiple domains on an end-to-end basis.
There are some basic differences between a route computation procedure for an inter-domain protocol and an intra-domain protocol:                1. Most of the protocols like OSPF and IS-IS which are employed with in an AS are link state protocols, hence the path computation is done locally. In contrast, protocols like the border gateway protocol (BGP), which are responsible for inter-domain routing, do path computation in a distributed way.        2. Since an AS falls under a single administrative domain, network administrators experience relatively little concern about policies, security, or exchange of resource and topology information between the routing elements. However, network administrators need to address these issues when conducting inter-domain routing.        3. Changes to a route computing method for an intra-domain protocol are easier to implement than for inter-domain protocol(s) as inter-domain protocols generally run in a distributed manner where there is a greater probability of forming routing loops due to any inconsistencies in the network. Inconsistencies typically occur due to link of node failures.        
Relevant to the development of a set of protocols that facilitate quality of service routing between domains is constraint based routing. Constraint based routing implies computing and signaling routes which satisfy a given set of constraints. These constraints can be classified based on the property of the link parameter they represent. Two types of constraints are link constraints, which need to be satisfied on a per link basis, and additive path constraints, where the sum of the corresponding parameter along the path from the source to the destination cannot exceed a pre-determined value.
These constraints have implications for the transport world largely due to the service level agreements (SLA's) between the carriers and the customers. In a packet switched network, network designers measure QoS parameters in terms of parameters such as available bandwidth, jitter, packet loss ratio, and end to end delay. But these measures of quality do not make much sense in the optical world since optical networks are inherently circuit switched.
For wavelength routed transparent networks, which carry data by modulating light, optical parameters, such as optical signal-to-noise ratio (OSNR), polarization mode dispersion (PMD), noise on a link, and cross talk between channels, need more attention. Thus, an inter-domain path computing procedure should take parameters such as these into consideration when calculating a path. Network designers can typically tolerate impairments associated with these parameters within a single AS since the distance between the source and the destination nodes are within some tolerable limit, but such impairments can become significant if the light that is carrying data spans multiple domains without any electronic conversion. Thus, protocols like BGP, if used as part of the control plane for inter-domain routing, should take such parameters into consideration.
Procedures currently exist that relate to computing constrained paths satisfying link constraints and an additive constraint, but these solutions are sequential and are appropriate when the path computation is done locally within a node. Intra-domain protocols, like OSPF, ISIS, do path computation on a local basis. Douglas Reeves and Hussein Salama in “A Distributed Algorithm for Delay-Constrained Unicast Routing, IEEE/ACM Transactions on Networking, Vol. 8, No. 2, April 2000, pp. 239-250, describe a distributed procedure, i.e., a delay constrained unicast routing (DCUR) procedure, to solve the RSP problem. However, the DCUR procedure does not fit into any of the current protocols used in computing paths. Thus, it would be difficult to extend currently used protocols to incorporate the DCUR procedure.